package main

import "fmt"

type MaxHeap struct {
	Data []any
}

func (m *MaxHeap) Left(i int) int {
	return 2*i + 1
}
func (m *MaxHeap) Right(i int) int {
	return 2*i + 2
}

func (m *MaxHeap) Parent(i int) int {
	return (i - 1) / 2
}

func (m *MaxHeap) Swap(i int, j int) {
	m.Data[i], m.Data[j] = m.Data[j], m.Data[i]
}

func (m *MaxHeap) Top() any {
	if len(m.Data) == 0 {
		return nil
	}
	return m.Data[0]
}

func (m *MaxHeap) Size() int {
	return len(m.Data)
}

func (m *MaxHeap) Empty() bool {
	return m.Size() == 0
}

func (m *MaxHeap) SiftUp(i int) {
	for {
		parent := m.Parent(i)
		if parent < 0 || m.Data[parent].(int) >= m.Data[i].(int) {
			break
		}

		m.Swap(parent, i)
		i = parent
	}

}

func (m *MaxHeap) Push(val any) {
	if val == nil {
		return
	}

	m.Data = append(m.Data, val)
	m.SiftUp(len(m.Data) - 1)
}

func (m *MaxHeap) SiftDown(i int) {
	// 通过i 获取 左右节点，判断哪个大就和哪个交换
	// 一直往下，直到左右节点大于整个数组长度
	for {
		left := m.Left(i)
		right := m.Right(i)
		max := i
		if left < m.Size() && m.Data[left].(int) > m.Data[i].(int) {
			max = left
		}
		if right < m.Size() && m.Data[right].(int) > m.Data[i].(int) {
			max = right
		}

		if max == i {
			break
		}

		m.Swap(i, max)
		i = max

	}

}

func (m *MaxHeap) Pop() (val any) {
	if m.Empty() {
		fmt.Println("max heap is empty")
		return nil
	}

	m.Swap(0, m.Size()-1)
	val = m.Data[m.Size()-1]
	m.Data = m.Data[:m.Size()-1]
	m.SiftDown(0)
	return val
}
